/**
 * 74. Search a 2D Matrix
 * https://leetcode.com/problems/search-a-2d-matrix/
 */
class SearchA2dMatrix {

    /**
     * 方法：二分查找
     * 将二维矩阵转化为一维数组进行二分查找。利用整除和取余运算将一维索引映射回二维
     * Args:
     *     matrix: List[List[int]], m x n 的二维矩阵
     *     target: int, 要搜索的
     * Returns:
     *     bool: 如果找到目标值返回True，否则返回Fa
     * Time: O(log(mn))，其中m和n分别是矩阵的行数
     * Space: O(1)，只使用常数额外空间
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0;
        int j = n - 1;
        while (i < m && j >= 0){
            if(matrix[i][j] == target){
                return true;
            }
            if(matrix[i][j] < target){
                i++;
            }else {
                j--;
            }
        }
        return false;
    }

    /**
     * 方法：Z字形查找
     *  从矩阵的右上角开始搜索。如果当前元素小于目标值，则向下移动；如果大于目标值，则向左移动。
     *  利用矩阵的有序性质，每次可以排除一行或一列
     *  Args:
     *      matrix: List[List[int]], m x n 的二维矩阵
     *      target: int, 要搜索的目标
     *  Returns:
     *      bool: 如果找到目标值返回True，否则返回Fals
     *  Time: O(m + n)，其中m和n分别是矩阵的行数和列数，最坏情况下需要遍历m+n个元
     *  Space: O(1)，只使用常数额外空间
     */
    public boolean searchMatrix1(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = -1;
        int right = m * n;
        while (left + 1 < right){
            int mid = (left + right) >>> 1;
            int x = matrix[mid / n][mid % n];
            if(x == target){
                return true;
            }
            if(x < target){
                left = mid;
            }else if (x > target){
                right = mid;
            }
        }
        return false;
    }
}